package demo2;

import java.util.Stack;

public class Sort {
    //插入排序
    public void insertSort1(int[] array){
        for(int i = 1; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    //插入排序
    public void insertSort2(int[] array){
        for(int i = 1; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    //插入排序
    public void insertSort3(int[] array){
        for(int i = 1 ; i < array.length; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    //希尔排序
    public void shell1(int[] array, int gap){
        for(int i = gap; i < array.length; i++){
            int key = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap){
                if(array[j] > key){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = key;
        }
    }
    public void shellSort1(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap /= 2;
            shell1(array, gap);
        }
        shell1(array, 1);
    }
    //希尔排序
    public void shell2(int[] array, int gap){
        for(int i = gap; i < array.length; i++){
            int key = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap){
                if(array[j] > key){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = key;
        }
    }
    public void shellSort2(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap /= 2;
            shell2(array, gap);
        }
        shell2(array, gap);
    }
    //希尔排序
    public void shell3(int[] array, int gap){
        for(int i = gap ; i < array.length; i++){
            int key = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap){
                if(array[j] > key){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = key;
        }
    }
    public void shellSort3(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap /= 2;
            shell3(array, gap);
        }
        shell3(array, 1);
    }
    //选择排序
    public void chooseSort(int[] array){
        for(int i = 0; i < array.length; i++){
            for(int j = i + 1; j < array.length; j++){
                if(array[i] > array[j]){
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
    //选择排序
    public void chooseSort2(int[] array){
        for(int i = 0; i < array.length; i++){
            for(int j = i + 1; j < array.length; j++){
                if(array[i] > array[j]){
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
    //冒泡排序
    public void bubbleSort(int[] array){
        for(int i = 0; i < array.length - 1; i++){
            boolean flag = false;
            for(int j = 0; j < array.length - i - 1; j++){
                if(array[j] > array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = true;
                }
            }
            if(!flag){
                break;
            }
        }
    }
  /*  //堆排序
    public void heapSort(int[] array){
        createBigHeap(array);
        int end = array.length - 1;
        while(end > 0){
            //这里不需要在判断大小，因为大根堆最上面本来就是最大的，直接交换即可
            swap(array, end, 0);
            adjustmentDown(array, 0, end);
            end--;
        }
    }
    //创建大根堆
    public void createBigHeap(int[] array){
        int len = array.length;
        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--){
            adjustmentDown(array, parent, len);
        }
    }
    //向下调整
    public void adjustmentDown(int[] array, int parent, int len){
        int child = parent * 2 + 1;
        while(child < len){
            //必须保证要有右孩子
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }
            if(array[parent] < array[child]){
                swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            }
            else{
                //如果根节点大于孩子结点后面就没必要比较了
                break;
            }
        }
    }
    //交换
    public void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
*/
/*    public void heapSort(int[] array){
        createBigHeap(array);
        int end = array.length - 1;
        while(end > 0){
            swap(array, 0, end);
            adjustmentDown(array, 0, end);
            end--;
        }
    }
    public void createBigHeap(int[] array){
        int len = array.length;
        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--){
            adjustmentDown(array, parent, len);
        }
    }
    public void adjustmentDown(int[] array, int parent, int len){
        int child = parent * 2 + 1;
        while(child < len){
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }
            if(array[parent] < array[child]){
                swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
    public void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }*/
    //堆排序
    public void heapSort(int[] array){
        createBigHeap(array);
        int end = array.length - 1;
        while(end > 0){
            swap(array, 0, end);
            adjustmentDown(array,0, end);
            end--;
        }
    }
    public void createBigHeap(int[] array){
        int len = array.length;
        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--){
            adjustmentDown(array, parent, len);
        }
    }
    public void adjustmentDown(int[] array, int parent, int len){
        int child = parent * 2 + 1;
        while(child < len){
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }
            if(array[parent] < array[child]){
                swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
    public void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //快速排序
    //插入排序
  /*  public void insertSort(int[] array, int start, int end){
        for(int i = start + 1; i <= end; i++){
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > key){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    //找基准
    public int fundPivot(int[] array,int start, int end){
        int key = array[start];
        while(start < end){
            //取等于号方式头尾元素相等造成死循环
            //tart < end再次判断是因为，有可能end这边的值都比key大，最后越界访问
            //一定要先从后面end遍历，最后结束位置的时候就把大的放前面了
            while(start < end && key <= array[end]){
                end--;
            }
            array[start] = array[end];
            while(start < end && array[start] <= key){
                start++;
            }
            array[end] = array[start];
        }
        //将基准放入停止时的位置
        array[start] = key;
        return start;
    }
    //寻找中间值交换
    public int funMidIndex(int[] array, int left, int right){
        int mid = (left + right) / 2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[right] < array[mid]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[left] < array[mid]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }
    //分组递归
    public void quick(int[] array, int left, int right){
        if(left >= right){
            return;
        }
        //这里相当于减少了7层递归
        if(right - left + 1 <= 7){
            insertSort(array, left, right);
        }
        int midIndex = funMidIndex(array, left, right);
        swap(array, left, midIndex);
        int pivot = fundPivot(array, left, right);
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }
    //充当个接口，同一传入的值为数组
    public void quickSort(int[] array){
        quick(array, 0, array.length - 1);
    }*/
    //非递归快排
    //寻找中间值交换
    public int funMidIndex(int[] array, int left, int right){
        int mid = (left + right) / 2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[right] < array[mid]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[left] < array[mid]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }
    //找基准
    public int fundPivot(int[] array,int start, int end){
        int key = array[start];
        while(start < end){
            //取等于号方式头尾元素相等造成死循环
            //tart < end再次判断是因为，有可能end这边的值都比key大，最后越界访问
            //一定要先从后面end遍历，最后结束位置的时候就把大的放前面了
            while(start < end && key <= array[end]){
                end--;
            }
            array[start] = array[end];
            while(start < end && array[start] <= key){
                start++;
            }
            array[end] = array[start];
        }
        //将基准放入停止时的位置
        array[start] = key;
        return start;
    }
    public void quickSort(int[] array){
        int left = 0;
        int right = array.length - 1;
        Stack<Integer> stack = new Stack<>();
        //三数取中法优化
        int midIndex = funMidIndex(array, left, right);
        swap(array, left, midIndex);
        int pivot = fundPivot(array, left, right);
        //若基准左边或右边的数据不超过一个，则将下标压入栈，否则就是有序
        if(left + 1 < pivot){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(right - 1 > pivot){
            stack.push(pivot + 1);
            stack.push(right);
        }
        //只要栈不为空，就每次弹出栈顶的两个元素作为左右边界，继续进行如上操作
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            midIndex = funMidIndex(array, left, right);
            swap(array, left, midIndex);
            pivot = fundPivot(array, left, right);
            if(left + 1 < pivot){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(right - 1 > pivot){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }

    }
    //归并排序
/*    private void mergeFunc(int[] array, int left, int right){
        if(left == right){
            return;
        }
        int mid = (left + right) / 2;
        //分解左边(包含mid下标元素)
        mergeFunc(array, left, mid);
        //分解右边
        mergeFunc(array, mid + 1, right);
        //合并
        merge(array, left, right, mid);
    }*/
    //合并
    private void merge(int[] array, int start, int end, int midIndex){
        int[] tmpArr = new int[end - start + 1];
        //tmpArr数组的零下标
        int k = 0;
        int s1 = start;
        int s2 = midIndex + 1;
        //两个同时比较
        while(s1 <= midIndex && s2 <= end){
            //这里因为是<=所以才是一个稳定的排序
            if(array[s1] <= array[s2]){
                tmpArr[k++] = array[s1++];
            }else{
                tmpArr[k++] = array[s2++];
            }
        }
        //若比较完后，还剩余一方未比较完，直接将剩下的一方拼上
        while(s1 <= midIndex){
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= end){
            tmpArr[k++] = array[s2++];
        }
        //把排好序的数字从start处开始拷贝回原数组
        for(int i = 0; i < k; i++){
            array[i + start] = tmpArr[i];
        }
    }
    public void mergeSort(int[] array){
        int gap = 1;
        while(gap < array.length){
            // i+= gap*2 是为了保证s1可以跳过e2、s2、e2到下一个待排序位置
            for(int i = 0; i < array.length; i += gap * 2){
                //首先能进循环i一定合法
                int s1 = i;
                int e1 = i + gap - 1;
                //注意保证指针不会越界！一旦越界采取强制措施，如下
                if(e1 > array.length - 1){
                    e1 = array.length - 1;
                }
                int s2 = e1 + 1;
                if(s2 > array.length - 1){
                    s2 = array.length - 1;
                }
                int e2 = s2 + gap - 1;
                if(e2 > array.length - 1){
                    e2 = array.length - 1;
                }
                merge(array, s1, e2, e1);
            }
            gap *= 2;
        }
    }
    public void countSort(int[] array){
        int maxIndex = array[0];
        int minIndex = array[0];
        for(int i = 0; i < array.length; i++){
            if(array[i] > maxIndex){
                maxIndex = array[i];
            }
            if(array[i] < minIndex){
                minIndex = array[i];
            }
        }
        //假设最大值66,最小值60,则有66 - 60 = 6个数据,而60~66实际上有7个数据，所以加一
        int[] countArr = new int[maxIndex - minIndex + 1];
        //开始计数
        for(int i = 0; i < array.length; i++){
            countArr[array[i] - minIndex]++;
        }
        //写入原数组
        int index = 0;//array的下标
        for(int i = 0; i < countArr.length; i++){
            while(countArr[i] != 0){
                array[index] = i + minIndex;
                countArr[i]--;
                index++;
            }
        }
    }











}
